package day_8_16;

/**
 * https://leetcode.cn/problems/design-add-and-search-words-data-structure/description/?envType=study-plan-v2&envId=top-interview-150
 * 211. 添加与搜索单词 - 数据结构设计
 */
public class Main2 {
    class WordDictionary {
        class Node {
            Node[] next = new Node[26];
            boolean isWord;
        }
        Node root;
        public WordDictionary() {
            root = new Node();
        }

        public void addWord(String word) {
            Node cur = root;
            for(int i = 0;i < word.length();i++) {
                int u = word.charAt(i) - 'a';
                if(cur.next[u] == null) {
                    cur.next[u] = new Node();
                }
                cur = cur.next[u];
            }
            cur.isWord = true;
        }

        public boolean search(String word) {
            return dfs(word,root,0);
        }

        private boolean dfs(String word,Node root,int index) {
            int n = word.length();
            if(index == n) {
                return root.isWord;
            }
            char ch = word.charAt(index);
            if(ch == '.') {
                for(int k = 0;k < 26;k++) {
                    if(root.next[k] != null && dfs(word,root.next[k],index + 1)) {
                        return true;
                    }
                }
                return false;
            }else {
                int u = ch - 'a';
                if(root.next[u] == null) {
                    return false;
                }
                // 说明这个 字符是存在的，往后遍历
                return dfs(word,root.next[u],index + 1);
            }
        }
    }
}
